Frequently, in a virtual environment, it is important to place objects like vehicles or pedestrians on the ground or to keep them on the ground as they move. Keeping them on the ground makes the environment seem more realistic.
More particularly, virtual environments are frequently designed to reflect the real world. Although gravity is not usually simulated in virtual environments, it is often desirable to keep moving objects and people on the ground to approximate the effects of gravity. While many virtual environment designers simplify the task of keeping things on the ground by using a flat ground plane, a hilly terrain can create a more interesting experience for the user. Note that for a virtual environment with 10 people roaming freely on a hilly terrain, this environment would require approximately 1200 (10 people.times.30 frames per sec.times.2 pts per foot front and back=1200) intersection calculations per second, leaving less than 1 millisecond for each intersection calculation. Of course, the actual calculation must take only a fraction of that time or the computer has no time left over to draw the graphics representing the environment on the screen. By way of example, it would be useful if each calculation took less than 20 usecs per point while examining tens of thousands of polygons. Note that 20 usecs corresponds to less than 3% of the computing power for the scenario involving 10 people in a single virtual environment.
As an example of virtual environments for which locating the ground is important, Diamond Park, a large and complex virtual reality environment, contains over 55,000 polygons. About 13,500 of those are terrain polygons. Note that terrain polygons are ground polygons which represent surfaces for moving around the environment. Bicyclists, unicyclists, and an acrobat and pedestrians all are to appear as if they were on the ground. This requires continuously calculating the location of the ground for each part of each object as it moves. Bikes require 4 ground intersections per frame and move at about 20 frames per second adding up to 80 calculations per second per bike.
The key to providing fast ground point calculation is to precalculate as much as possible and organize the polygons in a way that allows quick reduction in the number of floating point operations required to find the intersection point.
Knowing that a comparison operation can be an order of magnitude faster than a multiply or divide, e.g., 4 cycles for 1 compare operation, 16 cycles for 1 multiply, and 73 cycles for 1 divide on a 486 processor, even with hardware acceleration, polygons must be sorted by location before any intersection calculations are performed.